An essential semiconductor device is semiconductor memory, such as a random access memory (RAM) device. A RAM allows a memory circuit to execute both read and write operations on its memory cells. Typical examples of RAM devices include dynamic random access memory (DRAM) and static random access memory (SRAM).
Another form of memory is the content addressable memory (CAM) device. A CAM is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data in the comparand register) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers and switches, computer systems and other devices that require rapid content searching.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., DRAM and SRAM). For example, data is stored in a RAM in a particular location, called an address. During a memory access, the user supplies an address and reads into or gets back the data at the specified address.
In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected by an address bus, or the data can be written into the first empty memory location. Every location has at least one status bit that keeps track of whether the location is storing valid information in it or is empty and available for writing.
Once information is stored in a memory location, it is found by comparing every word in memory with data in the comparand register. When the content stored in the CAM memory location does not match the data in the comparand register, the local match detection circuit returns a no match indication. When the content stored in the CAM memory location matches the data in the comparand register, the local match detection circuit returns a match indication, e.g., a match flag. If one or more local match detection circuits return a match indication, the CAM device returns a “match” indication. Otherwise, the CAM device returns a “no-match” indication. In addition, the CAM may return the identification of the address location in which the desired data is stored or one of such addresses if more than one address contained matching data. Furthermore, if there is more than one match found, the CAM may return a multi-match signal, e.g., a multi-match flag. Thus, with a CAM, the user supplies the data and gets back an address if there is a match found in memory.
FIG. 1 shows a conventional CAM device 120 having a CAM bank 130, an address generator 140 and a priority encoder 150. The CAM bank 130 includes match detection circuits (not shown) that carry out the above-described match detection operation by comparing stored bits with comparand bits. The address generator 140 is coupled to the CAM bank 130 through line 145 and provides the address data corresponding to a particular memory location storing bits that match those in the comparand. A comparand data register 110, which stores the data being sought in the CAM, is coupled to CAM bank 130 through line 115.
The CAM bank 130 is also coupled to a priority encoder 150 through line 125 which determines and outputs the highest priority address that corresponds to the stored matching data within the CAM bank 130. Further, the priority encoder 150 outputs through line 131 then through line 135 a signal, e.g., a match flag signal, indicating whether a match detection circuit within the CAM bank 130 found a match between comparand data and stored data. As the CAM bank 130 may have more than one match the priority encoder 150 may also output, through line 131 then line 135, or through a separate line (not shown), another signal, e.g., a multi-match flag, indicating that multiple matches (i.e., multi-match) have been found. When a match is found in the CAM device 120, the CAM device 120 also outputs an address signal via line 155 corresponding to the highest priority address within the CAM device 120 that stored the matching data.
There are times when it is desirable to quickly search more words than are stored within a CAM bank 130. One solution is to cascade several CAM devices 120 to behave as a single CAM device that is larger than can be physically realized on a single chip. It is desirable that cascaded CAM devices 120 behave like a single CAM device 120, however, several problems can occur when cascading CAM devices.
One problem with cascading CAM devices 120 is that more than one of the cascaded CAM devices 120 may indicate a match, but only a single result is needed. If the cascaded CAM devices 120 are not controlled, then each of the CAM devices 120 having a match with the comparand data will attempt to return a result. The problem arises when a CAM device 120 having a relatively low priority attempts to return a result while a CAM device 120 having a relatively high priority is attempting to return a result at the same time. Therefore, a method for prioritizing cascaded CAM devices 120 has been implemented to indicate only the highest priority CAM device 120 having a match so that the highest priority CAM device 120 with a match provides its match results downstream.
A conventional cascaded CAM system 200 is shown is FIG. 2. As seen in FIG. 2, a cascaded CAM system 200 is implemented in the prior art by forming a “daisy” chain of CAM devices 220. In this embodiment, the highest priority CAM device 220 is the top-most CAM device 220 and the lowest priority CAM device 220 is the lowest CAM device 220. Each CAM device 220 has a respective match flag input pin 224 and a match flag output pin 225 (although only one of each type of pin is shown in FIG. 2).
The match flag output pin 225 of each CAM device is coupled to the match flag input pin 224 of the next CAM device 220. The first CAM device 220 in the chain, which may represent the highest priority addresses (e.g., lowest CAM index), has its match flag input pin 224 connected to a predetermined logic level external to the CAM device 220 to indicate that there is no previous CAM device. The match output pin 225 of the last CAM device 220 in the cascaded chain provides a system match flag 237, i.e., a global match flag, indicative of match conditions in the cascaded CAM device 220. Each CAM device 220 is coupled to receive data from the comparand register on line 115 and to send output data to a common data output bus 265 through a respective output line 155. Although not shown, a multi-match signal may also be cascaded through the CAM system 200 in a manner similar to the cascade of the match flag signal.
FIG. 3 shows one of the cascaded CAM devices 220 of FIG. 2 in greater detail. As seen in FIG. 3, each CAM device 220 is similar to CAM device 120 (of FIG. 1) but also includes a match priority encoder 260 and register 270. The match priority encoder 260 is used to prioritize CAM devices 220 that indicate a match. Match priority encoder 260 is coupled to and receives information through line 262 from another CAM device 220 coupled to match flag input pin 224. The input from match flag input pin 224 is coupled to the output of a match priority encoder 260 from a previous CAM device 220. Match priority encoder 260 also is coupled to and provides signal information, e.g., match flag signal and possibly multi-match signals, to pin 225 through line 261 and then from output pin 225 to the next CAM device 220 through line 135. As indicated above, the lowest priority CAM device 220 provides a match flag signal, which serves as the global match flag signal for the cascaded CAM configuration through line 237.
The priority encoder 150 is coupled and provides data to the register 270. If at least one match occurs in the match detection circuits of CAM device 220, then the priority encoder 150 determines the highest priority matching data and provides the address corresponding to that matching data to register 270 through line 253 where it is stored. Match priority encoder 260 is also coupled to register 270 through line 264. If match priority encoder 260 determines that the CAM device 220 is the highest priority CAM device 220 then match priority encoder 260 provides a signal, e.g., an enable signal, to register 270 to indicate thus. When register 270 receives the enable signal from match priority encoder 260, then register 270 provides the data stored at register 270 to line 155 which provides the address data to an output bus or a downstream circuit. Typically, each CAM device 220 contains the same range of addresses and therefore, high order address bits (or bit) are need to distinguish to match from a CAM with high priority and a match from a CAM with lower priority. Accordingly, register 270 may store not only the address of the matching word, but also these high order bits (or bit) to identify the CAM with priority.
With reference to FIGS. 2 and 3, the comparand data is provided on line 115 to each CAM device 220. In response to a search instruction, each CAM device 220 compares the comparand data with data stored in its respective CAM bank 130. If a priority encoder 150 detects a match between the comparand data and data stored in its CAM bank 130, priority encoder 150 sends a signal through line 231 to match priority encoder 260 indicating a match. If no match is found in CAM bank 130, then priority encoder 150 sends a signal to match priority encoder 260 indicating no match. Although shown as one line, line 125 is representative of a plurality of lines 125 between CAM block 130 and priority encoder 150. Match priority encoder 260 receives an input signal on line 262 from match flag input pin 224. If a CAM device 220 is the highest priority CAM device 220 in the cascaded CAM system 200, then a fixed, pre-programmed input signal is always provided to the input pin 224 of the CAM device 220. The pre-programmed input signal is set equivalent to a no-match signal and enables the highest priority CAM device 220 to determine if it is the highest priority CAM device 220 having a match (as described in greater detail below). If CAM device 220 is not the highest priority CAM device, then the signal input to the CAM device 220 from its match flag input pin 224 is the output from the match flag output pin 225 of the previous—the next higher—CAM device 220.
If the signal input by CAM device 220 from its match flag input pin 224 indicates a match, e.g., that a previous CAM device 220 had a match, then match priority encoder 260 provides a signal indicating a match on line 261 to its match flag output pin 225. If the signal input to CAM device 220 from its match flag input pin 224 indicates no match, i.e., that no prior CAM device 220 had a match, then match priority encoder 260 checks the signal provided by its priority encoder 150. If the signal provided by its priority encoder 150 indicates a match has been found, then match priority encoder 260 provides a signal indicating a match on line 261. If the signal provided by its priority encoder 150 indicates no match has been found, then match priority encoder 260 provides a signal indicating no match on line 261.
The highest priority CAM device 220 is at the top of the cascaded CAM system 200 (in FIG. 2) and the lowest priority CAM device 220 is at the bottom of the cascaded CAM system 200. The highest priority CAM device 220 having a match is determined in a top down process. The inherent layout architecture of the cascaded CAM system 200 prioritizes the CAM devices. For example, if a first CAM device 220 has a match, then the first CAM device 220 provides a signal indicating a match to match flag output pin 225. If the first CAM device 220 does not have a match, then the first CAM device 220 provides a signal indicating no-match to match flag output pin 225. The signal output by the first CAM device 220 is input to the next, a second, CAM device 220 in the cascaded CAM system 200. If the signal input to the second CAM device 220 indicates a match, i.e., that the first, higher CAM device 220 had a match, then the second CAM device 220 provides a signal to its match flag output pin 225 indicating a match. That signal is cascaded down to the remaining, lower priority, CAM devices 220, effectively preventing, or locking out, all the lower CAM devices 220.
A CAM device 220 acts according to the input received from match flag input pin 224. If the signal input on match flag input pin 224 to the second CAM device 220 does not indicate a match, i.e., that the first, higher CAM device 220 did not have a match, then the second CAM device 220 determines whether its CAM bank 130 has a match. If the match priority encoder 260 of the second CAM device 220 determines that a match occurred in its CAM bank 130, then the match priority encoder 260 of the second CAM device 220 provides a signal indicating a match to match flag output pin 225. If the match priority encoder 260 of the second CAM device 220 determines that no match occurred in its CAM bank 130, then the match priority encoder 260 of the second CAM device 220 provides a signal indicating no-match to match flag output pin 225. The lowest priority CAM device 220 in the cascade will only be able to determine if its associated CAM bank 130 has a match if no previous CAM devices 220 in the cascade have a match.
The highest priority CAM device 220 having a match provides its related data (e.g., address data, etc.) stored in register 270 to the common data output bus 265. The match priority encoder 260 of the highest priority CAM device 220 having a match provides a signal to its associated register 270 through line 264 which indicates that register 270 is permitted to provide its data on line 155. The remaining respective registers 270 of the other CAM devices 220 are not enabled to provide their respective address data to the common data output bus 265, therefore only a single CAM device 220 provides its data to the common data output bus 265. Although not shown, the cascaded CAM system 200 in FIG. 2 may also track whether multiple matches occur. Furthermore, address data provided to the common data output bus 265 may include other information in addition to the address data corresponding to the stored data that matched the comparand.
In the cascade CAM system 200, the lowest priority CAM device 220 must wait until the match flag signals from the previous CAM devices 220 have cascaded through each CAM device 220 in the cascaded chain before the global match flag 237 is generated. The time required to generate the global match flag 237, as well as the time required for the last CAM device 220 to resolve its match priority, is directly related to the number of cascaded devices 220. If the lowest priority CAM device 220 in the cascade has a match, it will be able to output its data to the common output bus 265 only if no other CAM devices 220 in the cascade, e.g., no previous, higher priority CAM devices 220, has a match. This may result in an undesirably long time to generate the system match flag 237 and for the last CAM device 220 to potentially output data to the common output bus 265 if the last CAM device 220 has a match, and no previous CAM device 220 has a match.
When a memory device (i.e., a memory circuit board) is manufactured which includes a cascaded CAM system 200 in a daisy chain, the CAM devices 220 are coordinated by programming each CAM device 220 with the same latency so that all of the CAM devices 220 run on the same clock cycle (or cycles). Since certain operations (e.g., reading, writing, or additional searching) cannot occur during the latency period, these operations are effectively held up on the cascaded CAM system 200 while awaiting results of the search from all of the CAM devices 220.
FIG. 4 shows another conventional approach to a cascaded CAM memory arrangement. The cascaded CAM system 400 of FIG. 4 attempts to decrease latency time in the system by providing the match flag signal of each CAM device 420 directly to all the other CAM devices 420 in the cascaded chain. As seen in FIG. 4, the match flag output signal that is carried on line 135 of each CAM device is coupled directly to the other CAM devices 220 in the cascade.
Turning now to FIG. 5, the CAM device 420 of FIG. 4 is shown in greater detail. The significant difference between CAM device 420 and CAM device 220 (of FIGS. 2 and 3) is the manner in which each CAM device determines priority. CAM device 420 includes a match priority encoder 460 which operates differently than the match priority encoder 260 of the CAM device 220 (FIG. 3). As described above, the CAM device 220 determines its match priority based on the input from the preceding CAM devices 220. However, each CAM device 420 receives match flag signal information directly from all other CAM devices 420 in the cascaded system (FIG. 4) and individually determines whether it is the highest priority CAM device 420 (described in greater detail below).
The priority encoder 150 is mutually coupled to and provides match flag signal information on line 131 to the match priority encoder 460 and provides the information to an output pin 225, which is coupled to line 135. Line 135 is mutually coupled to all other CAM devices 420 in the cascaded system 400 (FIG. 4). Although not shown, priority encoder 150 may be mutually coupled to and provide multi-match flag signal information to the match priority encoder 460 through an output pin.
CAM device 420 receives match flag signal information directly from all other CAM devices 420 through the input pin 224 and on line 262. The input from all other CAM devices 220 is hard wired; therefore, the match priority encoder 460 is able to identify which match flag signal corresponds to which CAM device 420. Each CAM device 420 is programmed with its priority relative to the other CAM devices 420. Therefore, a match priority encoder 460 in each CAM device 420 determines which, if any, match flag signals are received from higher priority CAM devices 420 and which, if any, match flag signals are received from lower priority CAM devices 420. Although not shown, multi-match flags may be similarly provided by each CAM device 420 to all the other respective CAM devices.
If a match priority encoder 460 has received a match flag signal from its priority encoder 150 and determines, based on the match flag signals received from the other CAM devices 420, that it is the highest priority CAM device 420 having a match, then the match priority encoder 460 provides a signal to the register 270. In response to the signal received from the priority encoder 460, register 270 provides address information that was stored in the register 270 to the common data output bus 265 through line 155 (FIGS. 4 and 5). As described above, register 270 may also provide higher order address bits.
CAM system 400 minimizes the latency associated with waiting for the match flag signal from respective CAM devices 420 to ripple through the cascaded chain, but increases the number of match flag input/output pins and associated circuitry required both within each and coupling each CAM device 420.
Therefore, there is a need for a CAM device that achieves a balance between the number of match flag input pins required per cascaded CAM system configuration and the latency time required to propagate match flag information to the other CAM devices of the cascaded CAM system. Preferably, the design of the CAM device would permit minimizing the number of pins required on the CAM device. Further, the design of the CAM device would minimize latency through a system of cascaded CAM devices.
The size of a cascaded CAM system, i.e., the number of CAM devices, suggests an appropriate CAM device to be used in the cascaded CAM system. As the size of the cascaded CAM system increases, the latency and/or the number of match flag input pins correspondingly increases. Thus, a CAM device chosen for use in a smaller-sized cascaded CAM system may be impractical or inefficient for use in a larger-sized cascaded CAM system.
Therefore, it is desirable to have a CAM device that would permit flexibility in the size of the cascaded CAM system without having to implement different CAM devices and that retains the number of match flag input pins and/or the speed of the smaller cascade system regardless of the number of cascaded CAM devices.